package main

import (
	"fmt"
	"stack"
	"util"
)

type G struct {
	index  int
	height int
}

/*
height: 2 1 0 1 3
index : 0 1 2 3 4

            __  3
__         |    2
  |__    __|    1
     |__|       0
0  1  2   3  4
*/
// [2  1  0  1
func trap(height []int) int {
	//n := len(height)
	s := stack.New()

	res := 0
	for i, h := range height {
		if s.Empty() {
			s.Push(G{i, h})
			continue
		}

		if h <= s.Top().(G).height {
			s.Push(G{i, h})
		} else {
			for {
				bottom := s.Pop().(G)
				if s.Empty() {
					break
				}

				left := s.Top().(G)
				//左右较小的高度与底部的高度差 * 这次计算的雨水宽度
				res += (util.Min(left.height, h) - bottom.height) * (i - left.index - 1)
				//左边高度小于右边高度才继续出栈
				if left.height >= h {
					break
				}
			}
			s.Push(G{i, h})
		}
	}

	return res
}

func main() {
	//s := stack.New()
	//s.Push(1)
	//s.Push(2)
	//s.Push(3)
	//fmt.Println(s.Empty(), s.Size())
	//fmt.Println(s)
	//a := s.Pop()
	//fmt.Println(a)
	//fmt.Println(s)
	//a = s.Pop()
	//fmt.Println(a)
	//fmt.Println(s)
	//a = s.Pop()
	//fmt.Println(a)
	//fmt.Println(s)
	//fmt.Println(s.Empty(), s.Size())
	heights := []int{2, 1, 0, 1, 3}
	res := trap(heights)
	fmt.Println(res)
}
